SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Subgradient method</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Subgradient method</span></span>

</h1>

</header>

<p><b>Subgradient methods</b> are <a href="Convex_optimization" title="Convex optimization">convex optimization</a> methods which use <a href="Subderivative" title="Subderivative">subderivatives</a>. Originally developed by <a href="Naum_Z._Shor" title="Naum Z. Shor">Naum Z. Shor</a> and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, sub-gradient methods for unconstrained problems use the same search direction as the method of <a href="Gradient_descent" title="Gradient descent">gradient descent</a>.

</p><p>Subgradient methods are slower than Newton's method when applied to minimize twice continuously differentiable convex functions. However, Newton's method fails to converge on problems that have non-differentiable kinks.

</p><p>In recent years, some <a href="Interior-point_methods" class="mw-redirect" title="Interior-point methods">interior-point methods</a> have been suggested for convex minimization problems, but subgradient projection methods and related bundle methods of descent remain competitive. For convex minimization problems with very large number of dimensions, subgradient-projection methods are suitable, because they require little storage.

</p><p>Subgradient projection methods are often applied to large-scale problems with decomposition techniques. Such decomposition methods often allow a simple distributed method for a problem.

</p>

<div class="mw-heading mw-heading2"><h2 id="Classical_subgradient_rules">Classical subgradient rules</h2></div>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./306c097f43c91dce633d12cde024948d39e73752.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.404ex; height:2.676ex;" alt="{\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"></span> be a <a href="Convex_function" title="Convex function">convex function</a> with domain <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}.}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}.}</annotation>

</semantics>

</math></span><img src="./76ef548febfc9981762740107858be9e3a5576c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.543ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}.}" loading="lazy"></span>

A classical subgradient method iterates

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }</annotation>

</semantics>

</math></span></span>

where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{(k)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{(k)}}</annotation>

</semantics>

</math></span><img src="./7851e5df97eb562a2088ad71e61402c07ff5efd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.486ex; height:3.176ex;" alt="{\displaystyle g^{(k)}}" loading="lazy"></span> denotes <i>any</i> <a href="Subgradient" class="mw-redirect" title="Subgradient">subgradient</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\ }</annotation>

</semantics>

</math></span><img src="./6ba5b1577da8634aff7f6868a9c1c9a1d83c37ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.859ex; height:2.509ex;" alt="{\displaystyle f\ }" loading="lazy"></span> at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(k)},\ }">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k)},\ }</annotation>

</semantics>

</math></span><img src="./6c46a7e9891b56637759a6178c0ed4913fc0e2da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.312ex; height:3.176ex;" alt="{\displaystyle x^{(k)},\ }" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(k)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k)}}</annotation>

</semantics>

</math></span><img src="./4c4ad77f04c0f250f01c3b6b5195ac5769d9dacf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.698ex; height:2.843ex;" alt="{\displaystyle x^{(k)}}" loading="lazy"></span> is the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{th}}</annotation>

</semantics>

</math></span><img src="./c348e1c6f8200f15d1d6026fc140d554b272096d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.984ex; height:2.676ex;" alt="{\displaystyle k^{th}}" loading="lazy"></span> iterate of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x.}</annotation>

</semantics>

</math></span><img src="./d07e9f568a88785ae48006ac3c4b951020f1699a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.977ex; height:1.676ex;" alt="{\displaystyle x.}" loading="lazy"></span>

If <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\ }</annotation>

</semantics>

</math></span><img src="./6ba5b1577da8634aff7f6868a9c1c9a1d83c37ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.859ex; height:2.509ex;" alt="{\displaystyle f\ }" loading="lazy"></span> is differentiable, then its only subgradient is the gradient vector <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nabla f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla f}</annotation>

</semantics>

</math></span><img src="./b7b4d6de89b52c5a5e6e1583cb63eaee263e307b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.214ex; height:2.509ex;" alt="{\displaystyle \nabla f}" loading="lazy"></span> itself.

It may happen that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -g^{(k)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -g^{(k)}}</annotation>

</semantics>

</math></span><img src="./c21fe610b526a31ae39e655933ad04f4765e1adc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.294ex; height:3.176ex;" alt="{\displaystyle -g^{(k)}}" loading="lazy"></span> is not a descent direction for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\ }</annotation>

</semantics>

</math></span><img src="./6ba5b1577da8634aff7f6868a9c1c9a1d83c37ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.859ex; height:2.509ex;" alt="{\displaystyle f\ }" loading="lazy"></span> at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(k)}.}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k)}.}</annotation>

</semantics>

</math></span><img src="./845cffd9bce394cffbb208279393b27e9bb4fa9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.345ex; height:2.843ex;" alt="{\displaystyle x^{(k)}.}" loading="lazy"></span> We therefore maintain a list <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{\rm {best}}\ }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{\rm {best}}\ }</annotation>

</semantics>

</math></span><img src="./179e1e7c699a1946d9bb4ec0aabf19d49158fce0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.884ex; height:2.509ex;" alt="{\displaystyle f_{\rm {best}}\ }" loading="lazy"></span> that keeps track of the lowest objective function value found so far, i.e.

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}.}</annotation>

</semantics>

</math></span></span>

</p>

<div class="mw-heading mw-heading3"><h3 id="Step_size_rules">Step size rules</h3></div>

<p>Many different types of step-size rules are used by subgradient methods. This article notes five classical step-size rules for which convergence <a href="Mathematical_proof" title="Mathematical proof">proofs</a> are known:

</p>

<ul><li>Constant step size, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}=\alpha .}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}=\alpha .}</annotation>

</semantics>

</math></span><img src="./1d89e86e55dac6d13ea9cdfe5a1810c6302a581f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.809ex; height:2.009ex;" alt="{\displaystyle \alpha _{k}=\alpha .}" loading="lazy"></span></li>

<li>Constant step length, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}</annotation>

</semantics>

</math></span><img src="./5dd307039b10e363cf562d34da43c35a88110a7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.612ex; height:3.343ex;" alt="{\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}" loading="lazy"></span> which gives <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}</annotation>

</semantics>

</math></span><img src="./40963109c5ba722300da3ce9ff6b072c67fbb395.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.723ex; height:3.343ex;" alt="{\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}" loading="lazy"></span></li>

<li>Square summable but not summable step size, i.e. any step sizes satisfying <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}</annotation>

</semantics>

</math></span></span></li>

<li>Nonsummable diminishing, i.e. any step sizes satisfying <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}">

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}</annotation>

</semantics>

</math></span></span></li>

<li>Nonsummable diminishing step lengths, i.e. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}</annotation>

</semantics>

</math></span><img src="./83e3041b61c41825fab4848abb4378fe62ac5c63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.643ex; height:3.343ex;" alt="{\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .}">

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .}</annotation>

</semantics>

</math></span></span></li></ul>

<p>For all five rules, the step-sizes are determined "off-line", before the method is iterated; the step-sizes do not depend on preceding iterations. This "off-line" property of subgradient methods differs from the "on-line" step-size rules used for descent methods for differentiable functions: Many methods for minimizing differentiable functions satisfy Wolfe's sufficient conditions for convergence, where step-sizes typically depend on the current point and the current search-direction. An extensive discussion of stepsize rules for subgradient methods, including incremental versions, is given in the books by Bertsekas<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and by Bertsekas, Nedic, and Ozdaglar.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Convergence_results">Convergence results</h3></div>

<p>For constant step-length and scaled subgradients having <a href="Euclidean_norm" class="mw-redirect" title="Euclidean norm">Euclidean norm</a> equal to one, the subgradient method converges to an arbitrarily close approximation to the minimum value, that is

</p>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }</annotation>

</semantics>

</math></span><img src="./c5648a79feca8b153788bfbf944dc186d72c4a97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.091ex; height:4.676ex;" alt="{\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }" loading="lazy"></span> by a result of <a href="Naum_Z._Shor" title="Naum Z. Shor">Shor</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></dd></dl>

<p>These classical subgradient methods have poor performance and are no longer recommended for general use.<sup id="cite_ref-Lem_4-0" class="reference"><a href="#cite_note-Lem-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-KLL_5-0" class="reference"><a href="#cite_note-KLL-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> However, they are still used widely in specialized applications because they are simple and they can be easily adapted to take advantage of the special structure of the problem at hand.

</p>

<div class="mw-heading mw-heading2"><h2 id="Subgradient-projection_and_bundle_methods">Subgradient-projection and bundle methods</h2></div>

<p>During the 1970s, <a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Claude Lemaréchal</a> and Phil Wolfe proposed "bundle methods" of descent for problems of convex minimization.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> The meaning of the term "bundle methods" has changed significantly since that time. Modern versions and full convergence analysis were provided by Kiwiel.

<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Contemporary bundle-methods often use "<a href="Level_set" title="Level set">level</a> control" rules for choosing step-sizes, developing techniques from the "subgradient-projection" method of Boris T. Polyak (1969). However, there are problems on which bundle methods offer little advantage over subgradient-projection methods.<sup id="cite_ref-Lem_4-1" class="reference"><a href="#cite_note-Lem-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-KLL_5-1" class="reference"><a href="#cite_note-KLL-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Constrained_optimization">Constrained optimization</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Projected_subgradient">Projected subgradient</h3></div>

<p>One extension of the subgradient method is the <b>projected subgradient method</b>, which solves the constrained <a href="Mathematical_optimization" title="Mathematical optimization">optimization</a> problem

</p>

<dl><dd>minimize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\ }</annotation>

</semantics>

</math></span><img src="./77f56c8f1e342b50fabd8459b7879ec0a6ad5d32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.998ex; height:2.843ex;" alt="{\displaystyle f(x)\ }" loading="lazy"></span> subject to <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in {\mathcal {C}}}</annotation>

</semantics>

</math></span></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"></span> is a <a href="Convex_set" title="Convex set">convex set</a>.

The projected subgradient method uses the iteration

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}</annotation>

</semantics>

</math></span></span>

where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> is projection on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{(k)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{(k)}}</annotation>

</semantics>

</math></span><img src="./7851e5df97eb562a2088ad71e61402c07ff5efd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.486ex; height:3.176ex;" alt="{\displaystyle g^{(k)}}" loading="lazy"></span> is any subgradient of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\ }</annotation>

</semantics>

</math></span><img src="./6ba5b1577da8634aff7f6868a9c1c9a1d83c37ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.859ex; height:2.509ex;" alt="{\displaystyle f\ }" loading="lazy"></span> at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(k)}.}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k)}.}</annotation>

</semantics>

</math></span><img src="./845cffd9bce394cffbb208279393b27e9bb4fa9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.345ex; height:2.843ex;" alt="{\displaystyle x^{(k)}.}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading3"><h3 id="General_constraints">General constraints</h3></div>

<p>The subgradient method can be extended to solve the inequality constrained problem

</p>

<dl><dd>minimize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{0}(x)\ }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{0}(x)\ }</annotation>

</semantics>

</math></span><img src="./19409b3d7d3fdd2fbdbbca76fdc8581af48cd9d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.913ex; height:2.843ex;" alt="{\displaystyle f_{0}(x)\ }" loading="lazy"></span> subject to <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}(x)\leq 0,\quad i=1,\ldots ,m}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}(x)\leq 0,\quad i=1,\ldots ,m}</annotation>

</semantics>

</math></span></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}}</annotation>

</semantics>

</math></span><img src="./65da883ca3d16b461e46c94777b0d9c4aa010e79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.509ex;" alt="{\displaystyle f_{i}}" loading="lazy"></span> are convex. The algorithm takes the same form as the unconstrained case

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }</annotation>

</semantics>

</math></span></span>

where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{k}>0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{k}>0}</annotation>

</semantics>

</math></span><img src="./d7cbfe8759a07d8b079f7dbc41cc28f580ea00c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.837ex; height:2.509ex;" alt="{\displaystyle \alpha _{k}>0}" loading="lazy"></span> is a step size, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{(k)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{(k)}}</annotation>

</semantics>

</math></span><img src="./7851e5df97eb562a2088ad71e61402c07ff5efd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.486ex; height:3.176ex;" alt="{\displaystyle g^{(k)}}" loading="lazy"></span> is a subgradient of the objective or one of the constraint functions at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x.\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x.\ }</annotation>

</semantics>

</math></span><img src="./b91ec8018c47e95c4931d9855e1a1ffbe1664f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.944ex; height:1.676ex;" alt="{\displaystyle x.\ }" loading="lazy"></span> Take

<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}">

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}</annotation>

</semantics>

</math></span></span>

where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \partial f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \partial f}</annotation>

</semantics>

</math></span><img src="./5e49e78bca168615a85789d3cbf71bb206b66430.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.597ex; height:2.509ex;" alt="{\displaystyle \partial f}" loading="lazy"></span> denotes the <a href="Subdifferential" class="mw-redirect" title="Subdifferential">subdifferential</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f.\ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f.\ }</annotation>

</semantics>

</math></span><img src="./d9ed92bbcd945496e4a6a6e1c92b8dd82feb0613.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.893ex; height:2.509ex;" alt="{\displaystyle f.\ }" loading="lazy"></span> If the current point is feasible, the algorithm uses an objective subgradient; if the current point is infeasible, the algorithm chooses a subgradient of any violated constraint.

</p>

<ul><li><a href="Stochastic_gradient_descent" title="Stochastic gradient descent">Stochastic gradient descent</a> – Optimization algorithm</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBertsekas2015" class="citation book cs1"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas, Dimitri P.</a> (2015). <i>Convex Optimization Algorithms</i> (Second ed.). Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-28-1</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFBertsekasNedicOzdaglar2003" class="citation book cs1">Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). <i>Convex Analysis and Optimization</i> (Second ed.). Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-886529-45-0</bdi>.</cite></span>

</li>

The approximate convergence of the constant step-size (scaled) subgradient method is stated as Exercise 6.3.14(a) in <a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas</a> (page 636): <cite id="CITEREFBertsekas1999" class="citation book cs1"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas, Dimitri P.</a> (1999). <i>Nonlinear Programming</i> (Second ed.). Cambridge, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-886529-00-0</bdi>.</cite> On page 636, Bertsekas attributes this result to Shor: <cite id="CITEREFShor1985" class="citation book cs1"><a href="Naum_Z._Shor" title="Naum Z. Shor">Shor, Naum Z.</a> (1985). <i>Minimization Methods for Non-differentiable Functions</i>. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-12763-1</bdi>.</cite></span>

</li>

<cite id="CITEREFLemaréchal2001" class="citation book cs1"><a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a> (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). <i>Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000</i>. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. <span class="nowrap">112–</span>156. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45586-8_4">10.1007/3-540-45586-8_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-42877-1</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1900016">1900016</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9048698">9048698</a>.</cite></span>

</li>

<cite id="CITEREFKiwielLarssonLindberg2007" class="citation journal cs1">Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). <a rel="nofollow" class="external text" href="http://rcin.org.pl/Content/139438/PDF/RB-2002-76.pdf">"Lagrangian relaxation via ballstep subgradient methods"</a> <span class="cs1-format">(PDF)</span>. <i><a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a></i>. <b>32</b> (3): <span class="nowrap">669–</span>686. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.1070.0261">10.1287/moor.1070.0261</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2348241">2348241</a>.</cite></span>

</li>

<cite id="CITEREFBertsekas1999" class="citation book cs1"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Bertsekas, Dimitri P.</a> (1999). <i>Nonlinear Programming</i> (Second ed.). Cambridge, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-886529-00-0</bdi>.</cite> </span>

</li>

<cite id="CITEREFKiwiel1985" class="citation book cs1">Kiwiel, Krzysztof (1985). <i>Methods of Descent for Nondifferentiable Optimization</i>. Berlin: <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>. p. 362. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3540156420</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0797754">0797754</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFBertsekas1999" class="citation book cs1">Bertsekas, Dimitri P. (1999). <i>Nonlinear Programming</i>. Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-886529-00-0</bdi>.</cite></li>

<li><cite id="CITEREFBertsekasNedicOzdaglar2003" class="citation book cs1">Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). <i>Convex Analysis and Optimization</i> (Second ed.). Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-886529-45-0</bdi>.</cite></li>

<li><cite id="CITEREFBertsekas2015" class="citation book cs1">Bertsekas, Dimitri P. (2015). <i>Convex Optimization Algorithms</i>. Belmont, MA.: Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-28-1</bdi>.</cite></li>

<li><cite id="CITEREFShor1985" class="citation book cs1">Shor, Naum Z. (1985). <i>Minimization Methods for Non-differentiable Functions</i>. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-12763-1</bdi>.</cite></li>

<li><cite id="CITEREFRuszczyński2006" class="citation book cs1"><a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński, Andrzej</a> (2006). <i>Nonlinear Optimization</i>. Princeton, NJ: <a href="Princeton_University_Press" title="Princeton University Press">Princeton University Press</a>. pp. xii+454. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0691119151</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2199043">2199043</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.stanford.edu/class/ee364a/">EE364A</a> and <a rel="nofollow" class="external text" href="http://www.stanford.edu/class/ee364b/">EE364B</a>, Stanford's convex optimization course sequence.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Convex_analysis_and_variational_analysis174" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Convex_analysis_and_variational_analysis174" style="font-size:114%;margin:0 4em"><a href="Convex_analysis" title="Convex analysis">Convex analysis</a> and <a href="Variational_analysis" title="Variational analysis">variational analysis</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_combination" title="Convex combination">Convex combination</a></li>

<li><a href="Convex_function" title="Convex function">Convex function</a></li>

<li><a href="Convex_set" title="Convex set">Convex set</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="List_of_convexity_topics" title="List of convexity topics">Topics (list)</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Choquet_theory" title="Choquet theory">Choquet theory</a></li>

<li><a href="Convex_geometry" title="Convex geometry">Convex geometry</a></li>

<li><a href="Convex_metric_space" title="Convex metric space">Convex metric space</a></li>

<li><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></li>

<li><a href="Duality_(optimization)" title="Duality (optimization)">Duality</a></li>

<li><a href="Lagrange_multiplier" title="Lagrange multiplier">Lagrange multiplier</a></li>

<li><a href="Legendre_transformation" title="Legendre transformation">Legendre transformation</a></li>

<li><a href="Locally_convex_topological_vector_space" title="Locally convex topological vector space">Locally convex topological vector space</a></li>

<li><a href="Simplex" title="Simplex">Simplex</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Maps</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_conjugate" title="Convex conjugate">Convex conjugate</a></li>

<li><a href="Concave_function" title="Concave function">Concave</a></li>

<li>(<a href="Closed_convex_function" title="Closed convex function">Closed</a></li>

<li><a href="Logarithmically_convex_function" title="Logarithmically convex function">Logarithmically</a></li>

<li><a href="Proper_convex_function" title="Proper convex function">Proper</a></li>

<li><a href="Pseudoconvex_function" title="Pseudoconvex function">Pseudo-</a></li>

<li><a href="Quasiconvex_function" title="Quasiconvex function">Quasi-</a>) <a href="Convex_function" title="Convex function">Convex function</a></li>

<li><a href="Invex_function" title="Invex function">Invex function</a></li>

<li><a href="Legendre_transformation" title="Legendre transformation">Legendre transformation</a></li>

<li><a href="Semi-continuity" title="Semi-continuity">Semi-continuity</a></li>

<li><a href="Subderivative" title="Subderivative">Subderivative</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Main results (list)</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Carath%C3%A9odory's_theorem_(convex_hull)" title="Carathéodory's theorem (convex hull)">Carathéodory's theorem</a></li>

<li><a href="Ekeland's_variational_principle" title="Ekeland's variational principle">Ekeland's variational principle</a></li>

<li><a href="Fenchel%E2%80%93Moreau_theorem" title="Fenchel–Moreau theorem">Fenchel–Moreau theorem</a></li>

<li><a href="Fenchel-Young_inequality" class="mw-redirect" title="Fenchel-Young inequality">Fenchel-Young inequality</a></li>

<li><a href="Jensen's_inequality" title="Jensen's inequality">Jensen's inequality</a></li>

<li><a href="Hermite%E2%80%93Hadamard_inequality" title="Hermite–Hadamard inequality">Hermite–Hadamard inequality</a></li>

<li><a href="Krein%E2%80%93Milman_theorem" title="Krein–Milman theorem">Krein–Milman theorem</a></li>

<li><a href="Mazur's_lemma" title="Mazur's lemma">Mazur's lemma</a></li>

<li><a href="Shapley%E2%80%93Folkman_lemma" title="Shapley–Folkman lemma">Shapley–Folkman lemma</a></li>

<li><a href="Ursescu_theorem#Robinson–Ursescu_theorem" title="Ursescu theorem">Robinson–Ursescu</a></li>

<li><a href="Ursescu_theorem#Simons'_theorem" title="Ursescu theorem">Simons</a></li>

<li><a href="Ursescu_theorem" title="Ursescu theorem">Ursescu</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Sets</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_hull" title="Convex hull">Convex hull</a></li>

<li>(<a href="Orthogonally_convex_set" class="mw-redirect" title="Orthogonally convex set">Orthogonally</a>, <a href="Pseudoconvexity" title="Pseudoconvexity">Pseudo-</a>) <a href="Convex_set" title="Convex set">Convex set</a></li>

<li><a href="Effective_domain" title="Effective domain">Effective domain</a></li>

<li><a href="Epigraph_(mathematics)" title="Epigraph (mathematics)">Epigraph</a></li>

<li><a href="Hypograph_(mathematics)" title="Hypograph (mathematics)">Hypograph</a></li>

<li><a href="John_ellipsoid" title="John ellipsoid">John ellipsoid</a></li>

<li><a href="Radial_set" title="Radial set">Radial set</a>/<a href="Algebraic_interior" title="Algebraic interior">Algebraic interior</a></li>

<li><a href="Zonotope" class="mw-redirect" title="Zonotope">Zonotope</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Series</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_series#Types_of_subsets" title="Convex series">Convex series related</a> (<a href="Convex_series#Types_of_subsets" title="Convex series">(cs, lcs)-closed</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(cs, bcs)-complete</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(lower) ideally convex</a>, <a href="Convex_series#Types_of_subsets" title="Convex series">(H<i>x</i>)</a>, and <a href="Convex_series#Types_of_subsets" title="Convex series">(Hw<i>x</i>)</a>)</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Duality_(optimization)" title="Duality (optimization)">Duality</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dual_system" title="Dual system">Dual system</a></li>

<li><a href="Duality_gap" title="Duality gap">Duality gap</a></li>

<li><a href="Strong_duality" title="Strong duality">Strong duality</a></li>

<li><a href="Weak_duality" title="Weak duality">Weak duality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Applications and related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convexity_in_economics" title="Convexity in economics">Convexity in economics</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

</ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-23" href="https://en.wikipedia.org/wiki/?title=Subgradient_method&oldid=1277290088">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>